package com.leetcode.test.tree;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * 层次遍历介绍  https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/8/
 */
public class 自己写的层次遍历 {

    @Test
    public void test() {
        Node f = new Node('F');
        Node b = f.left = new Node('B');
        Node g = f.right = new Node('G');
        Node a = b.left = new Node('A');
        Node d = b.right = new Node('D');
        Node i = g.right = new Node('I');
        Node c = d.left = new Node('C');
        Node e = d.right = new Node('E');
        Node h = i.left = new Node('H');

        List<Character> list = foo(f);

        Assert.assertEquals(Arrays.asList('F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'H'), list);
    }

    class Node {
        Node left;
        Node right;
        char val;

        public Node(char val) {
            this.val = val;
        }
    }

    List<Character> foo(Node root) {
        List<Character> list = new ArrayList<>();

        if (root == null) {
            return list;
        }

        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node node = queue.remove();

            list.add(node.val);

            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        return list;
    }

}
